//给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。 
//
// 你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。 
//
// 返回使用这些硬币能制造的 第 kᵗʰ 小 金额。 
//
// 
//
// 示例 1： 
//
// 
// 输入： coins = [3,6,9], k = 3 
// 
//
// 输出： 9 
//
// 解释：给定的硬币可以制造以下金额： 3元硬币产生3的倍数：3, 6, 9, 12, 15等。 6元硬币产生6的倍数：6, 12, 18, 24等。 9元硬
//币产生9的倍数：9, 18, 27, 36等。 所有硬币合起来可以产生：3, 6, 9, 12, 15等。 
//
// 示例 2： 
//
// 
// 输入：coins = [5,2], k = 7 
// 
//
// 输出：12 
//
// 解释：给定的硬币可以制造以下金额： 5元硬币产生5的倍数：5, 10, 15, 20等。 2元硬币产生2的倍数：2, 4, 6, 8, 10, 12等。 
//所有硬币合起来可以产生：2, 4, 5, 6, 8, 10, 12, 14, 15等。 
//
// 
//
// 提示： 
//
// 
// 1 <= coins.length <= 15 
// 1 <= coins[i] <= 25 
// 1 <= k <= 2 * 10⁹ 
// coins 包含两两不同的整数。 
// 
//
// Related Topics 位运算 数组 数学 二分查找 组合数学 数论 👍 11 👎 0


package leetcode.editor.cn;

import java.util.*;

class KthSmallestAmountWithSingleDenominationCombination {
    public static void main(String[] args) {
        Solution solution = new Solution();
    }

    static
//leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public long findKthSmallest(int[] coins, int k) {
            int min = Arrays.stream(coins).min().orElse(1);
            long left = k - 1, right = (long) min * k + 1;
            while (left + 1 < right) {
                long mid = (left + right) / 2;
                if (check(mid, coins, k)) {
                    right = mid;
                } else {
                    left = mid;
                }
            }
            return right;

        }

        /**
         * m范围类有coins组成的金额个数是否大于等于K个
         * 容斥原理
         */
        private boolean check(long m, int[] coins, int k) {
            long cnt = 0;
            next:
            for (int i = 1; i < (1 << coins.length); i++) { // 二进制形式枚举所有非空子集
                long lcmRes = 1; // 计算子集 LCM
                // 第i个coin是否在子集中
                for (int j = 0; j < coins.length; j++) {
                    if ((i >> j & 1) == 1) {
                        lcmRes = lcm(lcmRes, coins[j]);
                        if (lcmRes > m) { // 太大了
                            continue next;
                        }
                    }
                }
                cnt += Integer.bitCount(i) % 2 == 1 ? m / lcmRes : -m / lcmRes;
            }
            return cnt >= k;
        }

        /**
         * 最小公倍数
         */
        private long lcm(long a, long b) {
            return a * b / gcd(a, b);
        }

        /**
         * 最大公约数
         */
        private long gcd(long a, long b) {
            return a % b == 0 ? b : gcd(b, a % b);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}